// 待完成

package nachos.vm;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;

import java.util.*;

/**
 * 可以支持多个请求分页用户进程的内核
 */
public class VMKernel extends UserKernel {
    /**
     * 分配一个新的 VM 内核
     */
    public VMKernel() {
        super();

    }

    /**
     * 初始化这个内核
     */
    public void initialize(String[] args) {
        super.initialize(args);

        // 获取物理页数
        int numPhysPages = Machine.processor().getNumPhysPages();

        // 初始化页表、进程表和时钟标记位
        pageTable = new TranslationEntry[numPhysPages];
        pids = new int[numPhysPages];
        clockFlags = new boolean[numPhysPages];
        for (int i = 0; i < numPhysPages; i++) {
            pageTable[i] = new TranslationEntry(-1, i,
                    false, false, false, false);
            pids[i] = -1;
            clockFlags[i] = false;
        }

        // 初始化反向页表
        invertedPageTable = new Hashtable<>();

        lock = new Lock();
        condition = new Condition(lock);

        // 初始化交换区
        swap = new Swap();
    }

    /**
     * 测试这个内核
     */
    public void selfTest() {
        super.selfTest();
    }

    /**
     * 开始运行用户程序
     */
    public void run() {
        super.run();
    }

    /**
     * 终止此内核
     * 永不返回
     */
    public void terminate() {
        super.terminate();

        // 清空交换区
        swap.clear();
    }

    // 将 TLB 中页的状态同步到页表
    public static void copyTLBEntryStatus() {
        for (int i = 0; i < Machine.processor().getTLBSize(); i++) {
            copyTLBEntryStatus(i);
        }
    }

    // 通过时钟算法挑选页表项
    private static TranslationEntry selectEntryByClockAlgorithm() {
        TranslationEntry entry;

        // 循环遍历
        while (true) {
            // 指针指向下一页
            currentEntryIndex = (currentEntryIndex + 1) % pageTable.length;
            entry = pageTable[currentEntryIndex];

            if (entry.used) {
                continue;
            }

            if (!entry.valid) {
                break;
            }

            // 如果该值的标记为 true，则给它第 2 次机会
            if (!clockFlags[currentEntryIndex]) {
                break;
            }
            clockFlags[currentEntryIndex] = true;
        }

        return entry;
    }

    // 禁用指定页在 TLB 的映射项（如果存在的话）
    private static void invalidateTLBEntry(TranslationEntry memoryEntry) {
        for (int i = 0; i < Machine.processor().getTLBSize(); i++) {
            TranslationEntry TLBEntry = Machine.processor().readTLBEntry(i);
            if (TLBEntry.ppn == memoryEntry.ppn && TLBEntry.valid) {
                TLBEntry.valid = false;
                return;
            }
        }
    }

    // 从反向页表中移除该项
    private static void removeEntryFromInvertedPageTable(int pid, int vpn) {
        if (pids[currentEntryIndex] != -1) {
            invertedPageTable.remove(new TableKey(pid, vpn));
        }
    }

    // 清空化 entry 所指定的内存
    private static void clearMemory(TranslationEntry entry) {
        int address = Processor.makeAddress(entry.ppn, 0);
        Arrays.fill(Machine.processor().getMemory(),
                address, address + Processor.pageSize, (byte) 0);
    }

    // 向反向页表中添加映射
    private static void addEntryToInvertedPageTable(int pid, int vpn, TranslationEntry entry) {
        invertedPageTable.put(new TableKey(pid, vpn), entry);
    }

    // 获取一个空闲页
    public static TranslationEntry getFreePage(int pid, int vpn) {
        lock.acquire();

        // 如果页都处于使用状态，则等待
        while (usedCount == pageTable.length) {
            condition.sleep();
        }

        // 将 TLB 中页表项的状态同步到页表
        copyTLBEntryStatus();

        // 通过时钟算法挑选页表项
        TranslationEntry entry = selectEntryByClockAlgorithm();

        // 该页将被标记为正在使用
        usedCount++;

        // 如果该页表项也存在于 TLB 中，则把 TLB 中的页表项禁用
        invalidateTLBEntry(entry);

        // 将页表项从反向页表中移除
        removeEntryFromInvertedPageTable(pids[currentEntryIndex], entry.vpn);

        // 将移除的页置入交换区
        swap.add(pids[currentEntryIndex], entry);

        // 将该页格式化
        clearMemory(entry);

        // 根据参数修改页表项以及使用它的进程
        pids[currentEntryIndex] = pid;
        entry.vpn = vpn;

        // 将新的页表项添加到反向页表中
        addEntryToInvertedPageTable(pid, vpn, entry);

        lock.release();

        return entry;
    }

    // 从内存中获取页
    public static TranslationEntry getPageFromMemory(int pid, int vpn) {
        lock.acquire();

        // 获取页表项
        TranslationEntry entry = invertedPageTable.get(new TableKey(pid, vpn));

        if (entry != null) {
            // 将页表项设置为正在使用
            if (!entry.used) {
                entry.used = true;
                usedCount++;
            }
        }

        lock.release();

        return entry;
    }

    // 从交换区获取页
    public static TranslationEntry getPageFromSwap(int pid, int vpn) {
        // 判断指定页是否在交换区
        if (!swap.isContain(pid, vpn)) {
            return null;
        }

        // 将页从交换区取出
        return swap.remove(pid, getFreePage(pid, vpn));
    }

    // 将进程的所有页归还
    public static void releaseAllPage(int pid, int ownPageCount) {
        lock.acquire();

        // 释放该进程在内存中占用的空间
        for (int i = 0; i < ownPageCount; i++) {
            // 根据进程 id 和虚拟页号获取对应的页表项
            TranslationEntry entry = invertedPageTable.get(new TableKey(pid, i));

            // 将该页设置为空闲状态
            pids[entry.ppn] = -1;
            entry.valid = false;
        }

        lock.release();

        // 释放该进程在交换区中占用的空间
        swap.releaseProcess(pid, ownPageCount);
    }

    // 结束对某页的使用
    public static void releasePage(int ppn) {
        lock.acquire();

        // 获取页表项
        TranslationEntry entry = pageTable[ppn];

        // 将页表项设置为未在使用
        if (entry.used) {
            entry.used = false;
            usedCount--;
            condition.wake();
        }

        lock.release();
    }

    // 将 TLB 中指定页的状态同步到页表
    public static void copyTLBEntryStatus(int index) {
        // 获取 TLB 的项
        TranslationEntry TLBEntry = Machine.processor().readTLBEntry(index);

        if (!TLBEntry.valid) {
            return;
        }

        // 获取 TLB 项在页表中的对应项
        TranslationEntry memoryEntry = pageTable[TLBEntry.ppn];

        // 同步状态
        memoryEntry.used = TLBEntry.used;
        memoryEntry.dirty = TLBEntry.dirty;
    }

    // dummy variables to make javac smarter
    private static VMProcess dummy1 = null;

    private static final char dbgVM = 'v';

    // 页表
    private static TranslationEntry[] pageTable;

    // 反向页表
    private static Hashtable<TableKey, TranslationEntry> invertedPageTable;

    // 记录物理页的所属进程
    private static int[] pids;

    // 时钟标记
    private static boolean[] clockFlags;

    // 当前时钟的指针
    private static int currentEntryIndex = 0;

    // 正在使用中的页的数量
    private static int usedCount = 0;

    // 内存锁和条件变量
    private static Lock lock;
    private static Condition condition;

    // 交换区
    private static Swap swap;

    // 哈希表的键
    private static class TableKey {
        private int pid, vpn;

        private TableKey(int pid, int vpn) {
            this.pid = pid;
            this.vpn = vpn;
        }

        // 返回对象的哈希值，不同的哈希值可能影响查找元素的效率
        public int hashCode() {
            return pid * 10000 + vpn;
        }

        // 判断哈希表的键是否相同
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            } else if (obj instanceof TableKey) {
                return pid == ((TableKey) obj).pid && vpn == ((TableKey) obj).vpn;
            } else {
                return false;
            }
        }
    }

    // 交换区管理器
    private static class Swap {
        // 交换区对应的磁盘区域
        private OpenFile swapFile;

        // 记录进程与交换区数据的对应关系
        private Map<TableKey, SwapEntry> swapTable;

        // 保证哈希表的正确读写
        private Lock swapLock;

        // 存储暂时不用的页项，防止无限制的声明新的页，造成空间浪费
        private LinkedList<SwapEntry> freeSwapEntryList;

        // 交换项页号计数器，自增
        private int swapEntryCounter;

        // 对属性进行初始化
        private Swap() {
            swapFile = fileSystem.open("swap", true);
            swapTable = new Hashtable<>();
            swapLock = new Lock();
            freeSwapEntryList = new LinkedList<>();
        }

        // 将页从内存移入交换区
        private void add(int pid, TranslationEntry entry) {
            // 如果该页无效，则不必存储
            if (!entry.valid) {
                return;
            }

            swapLock.acquire();

            SwapEntry swapEntry = null;
            TableKey key = new TableKey(pid, entry.vpn);

            // 如果该页未存储于交换区且它被修改过，那么我们就需要保存它的状态，以便它再次使用
            if (entry.dirty || !swapTable.containsKey(key)) {
                // 如果有空闲的交换区空间，就继续使用
                if (freeSwapEntryList.size() != 0) {
                    swapEntry = freeSwapEntryList.removeFirst();
                    swapEntry.readOnly = entry.readOnly;
                }
                // 如果没有空闲交换区，就声明一块新的交换区空间
                else {
                    swapEntry = new SwapEntry(swapEntryCounter, swapEntry.readOnly);
                    swapEntryCounter++;
                }

                swapTable.put(key, swapEntry);
            }
            swapLock.release();

            // 将数据从内存写入到交换区
            if (swapEntry != null) {
                int pageSize = Processor.pageSize;
                swapFile.write(swapEntry.swapPageNum * pageSize,
                        Machine.processor().getMemory(), entry.ppn * pageSize, pageSize);
            }
        }

        // 将页从交换区移入内存
        private TranslationEntry remove(int pid, TranslationEntry entry) {
            swapLock.acquire();

            // 尝试在交换区中获取该页的信息
            SwapEntry swapEntry = swapTable.get(new TableKey(pid, entry.vpn));

            swapLock.release();

            // 如果该页未在交换区中
            if (swapEntry == null) {
                return null;
            }

            // 将数据从交换区读入到内存
            int pageSize = Processor.pageSize;
            swapFile.read(swapEntry.swapPageNum * pageSize,
                    Machine.processor().getMemory(), entry.ppn * pageSize, pageSize);
            pageTable[entry.ppn].readOnly = swapEntry.readOnly;

            return entry;
        }

        // 判断该页是否存在于交换区中
        private boolean isContain(int pid, int vpn) {
            swapLock.acquire();

            boolean isContain = swapTable.containsKey(new TableKey(pid, vpn));

            swapLock.release();

            return isContain;
        }

        // 将某个进程在交换区存放的数据清理掉
        private void releaseProcess(int pid, int ownPageCount) {
            swapLock.acquire();

            // 对于进程来说，虚拟内存是连续的，只需要传入最大虚拟内存页号即可
            SwapEntry entry;
            for (int i = 0; i < ownPageCount; i++) {
                // 尝试从交换区中获取交换项
                entry = swapTable.get(new TableKey(pid, i));

                // 将空闲的交换项存储起来，避免空间浪费
                if (entry != null) {
                    freeSwapEntryList.add(entry);
                }
            }

            swapLock.release();
        }

        // 清空交换区
        private void clear() {
            // 关闭并删除交换区文件
            swapFile.close();
            fileSystem.remove(swapFile.getName());
        }
    }

    // 交换项，记录交换区页号（能计算出对应的地址）和该页是否只读
    private static class SwapEntry {
        private int swapPageNum;
        private boolean readOnly;

        SwapEntry(int swapPageNum, boolean readOnly) {
            this.swapPageNum = swapPageNum;
            this.readOnly = readOnly;
        }
    }
}
